package com.jdaw.datastructure.avl;

public class AVLTreeDemo {
    public static void main(String[] args) {
        int arr[]={10,11,8,9,7,6};
        AVLTree avlTree=new AVLTree();
        for(int i=0;i<arr.length;i++){
            avlTree.add(new Node(arr[i]));
        }
        avlTree.midOrder();
        System.out.println(avlTree.root.leftHeight());
        System.out.println(avlTree.root.rightHeight());
        System.out.println(avlTree.root.right);
        System.out.println(avlTree.root.left);
    }
}

class AVLTree{
Node root;

    //查找要删除的节点
    public Node search(int value){
        if(root==null){
            return null;
        }else{
            return root.search(value);
        }
    }

    //查找要删除的节点的父结点
    public Node searchParent(int value){
        if(root==null){
            return null;
        }else{
            return root.searchParent(value);
        }
    }

    //删除有两个子树的节点的方法：找到右子树中最小的节点
    public int delRightTreeMin(Node node){
        //node是传入的二叉排序树的根节点，就是要删除的结点，返回的int是最小的结点的值
        Node target=node;
        //循环查找左子树就能找到最小值
        while(target.left!=null){
            target=target.left;
        }
        delNode(target.value);
        return target.value;
    }

    //删除
    public void delNode(int value){
        if(root==null){
            return;
        }else{
            Node targetNode=search(value);
            if(targetNode==null){
                return;
            }
            //根节点
            if(root.left==null&&root.right==null){
                root=null;
                return;
            }

            //找targetNode的父结点
            Node parent=root.searchParent(value);
            //1.叶子结点的删除
            if(targetNode.left==null&&targetNode.right==null){
                if(parent.left!=null&&parent.left.value==value){
                    parent.left=null;
                }else if(parent.right!=null&&parent.right.value==value){
                    parent.right=null;
                }
            }else if(targetNode.left!=null&&targetNode.right!=null){
                //2.有两颗子树的结点的删除
                int minVal=delRightTreeMin(targetNode.right);
                targetNode.value=minVal;
            }else{
                //3.删除只有一颗子树的结点
                //有左子节点
                if(targetNode.left!=null){
                    if(parent!=null) {
                        if (parent.left.value == value) {
                            parent.left = targetNode.left;
                        } else {
                            parent.right = targetNode.left;
                        }
                    }else{
                        root=targetNode.left;
                    }
                }else{
                    if(parent!=null) {//可能出现只有两个节点的情况
                        if (parent.left.value == value) {
                            parent.left = targetNode.right;
                        } else {
                            parent.right = targetNode.right;
                        }
                    }else{
                        root=targetNode.right;
                    }
                }
            }
        }
    }

    public void midOrder(){
        if(root!=null){
            root.midOrder();
        }else{
            System.out.println("二叉排序树为空");;
        }
    }

    public void add(Node node){
        if(root!=null){
            root.add(node);
        }else{
            root=node;
        }
    }
}


class Node{
    int value;
    Node left;
    Node right;

    public Node(int value) {
        this.value = value;
    }

    @Override
    public String toString() {
        return "Node{" +
                "value=" + value +
                '}';
    }

    //返回左子树的高度
    public int leftHeight(){
        if(left==null){
            return 0;
        }else{
            return left.height();
        }
    }

    //返回右子树的高度
    public int rightHeight(){
        if(right==null){
            return 0;
        }else{
            return right.height();
        }
    }

    //左旋转
    public void leftRotate() {
        Node newNode=new Node(value);
        newNode.left=left;
        newNode.right=right.left;
        value=right.value;
        right=right.right;
        left=newNode;
    }

    //右旋转
    public void rightRotate() {
        Node newNode=new Node(value);
        newNode.right=right;
        newNode.left=left.right;
        value=left.value;
        left=left.left;
        right=newNode;
    }

    //返回结点为根结点的树的高度
    public int height(){
        return Math.max(left==null?0:left.height(),right==null?0: right.height())+1;
    }

    //查找要删除的节点
    public Node search(int value){
        if(value==this.value){
            return this;
        }else if(value<this.value){
            if(this.left!=null) {
                return this.left.search(value);
            }else{
                return null;
            }
        }else {
            if(this.right!=null) {
                return this.right.search(value);
            }else{
                return null;
            }
        }
    }
    //查找要删除的节点的父结点
    public Node searchParent(int value){
        if((this.left!=null&&value==this.left.value)||(this.right!=null&&value==this.right.value)){

            return this;
        }else{
            if(value<this.value&&this.left!=null){
                return this.left.searchParent(value);
            } else if(value>=this.value&&this.right!=null){
                return this.right.searchParent(value);
            }else {
                return null;
            }
        }
    }

    //添加节点
    public void add(Node node){
        if(node==null){
            return;
        }
        if(node.value>this.value){
            if(this.right==null){
                this.right=node;
            }else{
                this.right.add(node);
            }
        }else{
            if(this.left==null){
                this.left=node;
            }else{
                this.left.add(node);
            }
        }

        //添加完节点后进行判断是否要旋转
        //左旋转
        if(leftHeight()-rightHeight()<-1){
            if(right!=null&&right.left.height()>right.right.height()){
                left.rightRotate();
            }
            leftRotate();
            return;
        }
        if(leftHeight()-rightHeight()>1){
            if(left!=null&&left.right.height()>left.left.height()){
                left.leftRotate();
            }
            rightRotate();
            return;
        }
    }

    //中序遍历
    public void midOrder(){
        if (this.left != null) {
            this.left.midOrder();
        }
        System.out.println(this);
        if (this.right != null) {
            this.right.midOrder();
        }
    }
}